#ifndef _ASTAR_H_
#define _ASTAR_H_

#include "Grid.h"
#include <queue>

#define astar_priority_queue priority_queue<GridCoord*,vector<GridCoord*>,AStar>

class AStar {
   private:
      // Contains a mapping from a grid coordinate to the path distance
      // travelled to reach that point (g) and the estimated cost to reach
      // the destination (h). These objects are static so that they
      // can be used in the priority_queue defined above.
      static map<const GridCoord*,double> g,h;
      
      // Contains a mapping from a grid coordinate to the current state of
      // the grid coordinate.
      map<const GridCoord*,GridCoord::SearchState> states;
      Grid *grid;

      // Calls grid->dist_between() to calculate the heuristif for point h.
      inline double calcHeuristic(const GridCoord *from,const GridCoord *to);
      
      // Returns the path to follow to get from start to finish. This iterates
      // over the 'from' variables for each of the coordinates from goal to
      // start.
      list<GridCoord*> get_path(GridCoord *at);
      
      // Getter functions
      static double getF(const GridCoord *at);
      static double getG(const GridCoord *at);
      static double getH(const GridCoord *at);
      GridCoord::SearchState getState(const GridCoord *at);
      
      // Setter functions
      void setG(const GridCoord *at,double val);
      void setH(const GridCoord *at,double val);
      void setH(const GridCoord *at,const GridCoord *goal);
      void setState(const GridCoord *at,GridCoord::SearchState val);
      
      // Resorts the priority queue by removing all elements from it and placing
      // them back in. This is necessary when the path cost of a grid coordinate
      // in the queue changes as a result of finding a shorter path. 
      void resort_queue(astar_priority_queue *queue);
      
   public:
      // Empty constructor. Used in the priority_queue.
      AStar(){}
      
      // construct the AStar object with the given grid.
      AStar(Grid *grid);
      // Various methods for performing a search from start to goal.
      
      list<GridCoord*> search(Coord start,Coord goal);
      list<GridCoord*> search(DCoord start,DCoord goal);
      list<GridCoord*> search(GridCoord *start,GridCoord *goal);
      
      // Used with the priority queue to compare two grid coordinates.
      bool operator()(const GridCoord *s1,const GridCoord *s2);
};

#endif
